package com.chen.demo.javase.algorithm.leetcode.editor.cn;
//给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。 
//
// 示例 1: 
//
// 输入: 1->2->3->4->5->NULL, k = 2
//输出: 4->5->1->2->3->NULL
//解释:
//向右旋转 1 步: 5->1->2->3->4->NULL
//向右旋转 2 步: 4->5->1->2->3->NULL
// 
//
// 示例 2: 
//
// 输入: 0->1->2->NULL, k = 4
//输出: 2->0->1->NULL
//解释:
//向右旋转 1 步: 2->0->1->NULL
//向右旋转 2 步: 1->2->0->NULL
//向右旋转 3 步: 0->1->2->NULL
//向右旋转 4 步: 2->0->1->NULL 
// Related Topics 链表 双指针 
// 👍 390 👎 0

import java.util.Scanner;

public class RotateList {
    public static void main(String[] args) {
        Solution solution = new RotateList().new Solution();
        ListNode head = initList("");
        System.out.println("请输入k:{}");
        Scanner scanner = new Scanner(System.in);
        printList(solution.rotateRight(head,Integer.parseInt(scanner.nextLine())));
    }

//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public static ListNode initList(String listNo) {
        System.out.println("链表长度:");
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int length = Integer.parseInt(s);
        ListNode head = null;
        ListNode temp = null;
        System.out.println("以此输入链表数据:");
        while (length > 0) {
            if (head == null) {
                temp = new ListNode(Integer.parseInt(scanner.next()));
                head = temp;
            } else {
                temp.next = new ListNode(Integer.parseInt(scanner.next()));
                temp = temp.next;
            }

            length--;
        }
        return head;
    }

    public static void printList(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print("" + temp.val + " ");
            temp = temp.next;
        }
        System.out.println("");
    }
    class Solution {
        /**
         * 解决思路:
         * 1:先将链表形成环
         * 2:新链表的头部位于：(length-k) % length
         *
         * @param head
         * @param k
         * @return
         */
        public ListNode rotateRight(ListNode head, int k) {
            // 空，或者只有一个节点
            if (head == null || head.next == null) {
                return head;
            }
            ListNode fast = head;
            ListNode slow = head;
            int length = 1;
            while (fast.next != null) {
                length++;
                fast = fast.next;
            }
            // 构建成环
            fast.next = head;
            int step = length - k %length;
            // 最后一步，拆分环形链表
            while (step > 1){
                //
                slow = slow.next;
                step--;
            }
            ListNode tmp = slow;
            slow = slow.next;
            // 将环拆开，形成单链表
            tmp.next=null;
            return slow;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}